package everydayone.isSymmetric;

import java.util.LinkedList;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @date 2020/05/31
 * @author 王光浩
 * @thinking 使用迭代模式
 * @Analysis 时间复杂度O（n），空间复杂度O（n）
 */
public class MyMethodTwo {
	
	public boolean isSymmetric(TreeNode root) {
		if (root == null)
			return true;
		LinkedList<TreeNode> stack1 = new LinkedList<TreeNode>(); //保存正常的前序遍历节点
		LinkedList<TreeNode> stack2 = new LinkedList<TreeNode>(); //保存镜像后前序遍历节点
		stack1.addLast(root);
		stack2.addLast(root);
		//迭代判断是否镜像
		while(!stack1.isEmpty() || !stack2.isEmpty()) {
			TreeNode node1 = stack1.pollLast();
			TreeNode node2 = stack2.pollLast();
			if (node1 == null && node2 == null)
				continue;
			//不对称直接返回false
			if (node1 == null || node2 == null || node1.val != node2.val)
				return false;			
			stack1.addLast(node1.right);
			stack2.addLast(node2.left);			
			stack1.addLast(node1.left);
			stack2.addLast(node2.right);
		}
		return true;
	}
}
